FIG. 1 illustrates a structure of a mobile communication channel to which the present invention and the related art are applied. Hereinafter, the structure of the mobile communication channel will be described with reference to FIG. 1. A transmitter undergoes a channel coding procedure to transmit data without loss or distortion through a radio channel. Examples of the channel coding include convolutional coding, turbo coding, LDPC coding, etc. The data which has undergone the channel coding procedure can be transmitted to the radio channel as a single symbol which includes several bits. At this time, a procedure of mapping several bits to a single symbol is referred to as modulation.
The modulated data is converted into a signal for multiple transmission through a multiplexing procedure or a multiple access method. Examples of the multiplexing procedure include CDM, TDM, FDM, etc. An example of OFDM (Orthogonal Frequency Division Multiplexing) is shown in FIG. 1. The signal which has undergone the multiplexing block is changed to a structure suitable for transmission to one or more multi-antennas, and then is transferred to a receiver through the radio channel. Fading and thermal noise occur in the transmitted data when the data passes through the radio channel. For this reason, distortion may occur in the data.
The modulated data is transferred to the receiver through the radio channel. In this case, fading and thermal noise occur in the transmitted data, whereby distortion may occur therein. The receiver performs a series of procedures of the transmitter in reverse order after receiving the distorted data. The receiver performs demodulation to convert the data mapped to the symbol into a bit stream, undergoes channel decoding, and restores the distorted data to the original data.
An apparatus of performing the channel coding stores a matrix H or a matrix G, wherein the matrix H is a parity check matrix used to generate parity bits to be added to input data (systematic bits), and the matrix G is a parity check generate matrix derived from the matrix H. In other words, the transmitter includes an encoder which generates parity bits through the input data and the matrix H or G. An apparatus of performing channel decoding checks whether the systematic bits are restored well, through operation of the received data (distorted systematic bits+parity bits) with the matrix H, and performs operation again if the systematic bits are failed to be restored.
Examples of the modulation include BPSK (Binary Phase Shift Keying), QPSK (Quadrature Phase Shift Keying), 16-QAM (Quadrature Amplitude Modulation), 64-QAM, 256-QAM, etc. For example, 16-QAM maps the data stream which has undergone channel encoding to a single symbol in a unit of 4 bits during modulation. 16-QAM demaps the single symbol received through the radio channel four bits during demodulation.
Hereinafter, a data retransmission method that can be used along with the present invention will be described. There are provided various examples of the data retransmission method. Of them, HARQ (Hybrid Automatic Repeat reQuest) method will be described. The HARQ scheme is obtained by combination of FEC (Forward Error Correction) symbol and ARQ (Automatic Repeat reQuest) which is a retransmission method in a mobile communication system. According to the ARQ method, if error is detected from data received by the receiver, the receiver requests retransmission to a transmitter. Examples of the ARQ method include Stop-And-Wait, Selective Repeat, Go-Back-N, etc. depending on the retransmission method. According to the Stop-And-Wait method, as shown in FIG. 2, if the transmitter receives an acknowledgement (ACK) message from the receiver after transmitting data, the transmitter transmits next data, wherein ACK message notifies that the receiver has successfully received the data. If the transmitter receives a NACK message from the receiver, wherein NACK message notifies that the receiver has failed to successfully receive the data, the transmitter retransmits the failed data.
Meanwhile, according to the Go-Back-N method, the transmitter first transmits N number of data and receives ACK messages from the receiver in due order. FIG. 3 illustrates a case of N=7, wherein the number N of data which are transmitted without ACK message is referred to as a window size. If the transmitter receives NACK message in response to the kth data, the transmitter sequentially transmits data starting from the kth data.
FIG. 4 illustrates a Selective Repeat method. According to the Selective Repeat method, like the Go-Back-N method, the number N of data which are transmitted without ACK or NACK message is referred to as a window size, and retransmission is selectively performed for only data with NACK message.
According to the aforementioned HARQ scheme, if retransmission is performed in the ARQ method, previously transmitted data is combined with retransmitted data to restore the data through FEC symbol. The HARQ scheme is classified into a chase combining method and an incremental redundancy method depending on a combining method of the two data. According to the chase combining method, as shown in FIG. 5, the receiver combines transmission data with retransmission data to increase a receiving signal to noise ratio (SNR), thereby increasing a receiving success ratio of data at the receiver.
Meanwhile, unlike the chase combining method, the incremental redundancy method (hereinafter, referred to as ‘IR method’) transmits some of encoded data, which have not been used for first transmission, during retransmission of the transmitter to decrease a coding rate of data received at the receiver, thereby increasing a receiving success ratio.
Hereinafter, LDPC coding will be described. A concept of LDPC coding is as follows.
A linear code can be described with the parity check generation matrix G and the parity check matrix H. A characteristic of the linear code is that the equation of HcT=0 is satisfied for every bit of a codeword ‘c’. As one of the linear code, the LDPC code which is recently paid attention to was proposed by Gallager in 1962 for the first time. One of the characteristics of the LDPC coding is that most of elements of the parity check matrix H are ‘0’ and the number of elements which are not ‘0’ is small compared to the codeword, so that repetitive decoding based on probability is possible. A parity check matrix H for the first proposed LDPC code was defined in a non-systematic form and each row and column of the parity check matrix were designed to equally have a small weight.
In this case, the weight means the number of ‘1’ included in each row and column.
The LDPC coding scheme has low decoding complexity since a density of elements which are not ‘0’ in the parity check matrix H is low. Further, decoding performance of the LDPC coding is superior to other coding schemes, which is adjacent to the theoretical limit of Shannon. However, the LDPC coding scheme could not be implemented with the hardware technique at the time of proposal by Gallegar, so that the LDPC coding scheme has not been paid attention to by the people for 30 years. A repetitive decoding scheme using graphs was developed in early 1980's and a couple of decoding algorithms for the LDPC code have been developed using the repetitive decoding scheme. One of them is a sum-product algorithm.
The LDPC coding has a superior error correction capability, thereby improving communication speed and capacity. When combined with a multi-input and multi-output (MIMO) scheme, the LDPC coding can be applied to a high speed wireless LAN having a data transmission speed of several hundred Mbit/s, a high speed mobile communication system having a data transmission speed of one Mbit/s for a user moving at a speed of 250 km/h, and an optical communication system having a data transmission speed of 40 Gbit/s. In addition, the LDPC coding can enable a quantum encryption communication diminishing the number of retransmission on a communication path having low quality since transmission quality is improved due to its high error correction capability. Further, data packets having errors can be easily recovered due to the low complexity and superior loss compensation capability of the LDPC coding, so that contents having quality equal to that of TV can be transmitted through the Internet and the mobile communication system. 10G BASE-T transmission within a range of 100 m which has been considered impossible earlier can be realized owing to wide application range and large capacity which are advantages of the LDPC coding. In addition, transmission capacity of a single satellite transmitter having 36 MHz bandwidth can be increased up to 80 Mbit/s which is 1.3 times of usual transmission capacity. With the above described advantages, the LDPC coding scheme is adopted as a next generation coding scheme in a communication system, like IEEE 802.16 or IEEE 802.11, etc.
Hereinafter, a structured LDPC will be described.
A parity check matrix H is used in the LDPC encoding and decoding method, and includes most of elements 0 and some elements 1. Since the matrix H has a great size of 105 bits or greater, a large sized memory is required to express the matrix H. The structured LDPC expresses the elements of the matrix H used for LDPC encoding and decoding as a sub-block of a certain size as shown in FIG. 7. In IEEE 802.16e, the sub-block is expressed by one integer index to decrease the size of the memory required to store the matrix H. Various kinds of matrixes could be the sub-block. For example, a permutation matrix of a certain size could be the sub-block.
If the structured LDPC is used, one integer (i.e., index) is only needed to be stored in a specific memory instead of a certain sized matrix consisting of elements of 1 or 0. Accordingly, the size of the memory required to express the matrix H can be decreased.
For example, if a size of a codeword reflected in the IEEE802.16e standard is 2304 and a coding rate is 2/3, a model matrix used for LDPC encoding/decoding is as shown in FIG. 8.
As shown in FIG. 8, the structured LDPC matrix of IEEE802.16e consists of elements of −1, 0 and positive integers, wherein −1 represents a zero matrix of which elements are all 0, and 0 represents an identity matrix. The positive integers excluding −1 and 0 constitute a permutation matrix in which the identity matrix is shifted to the right by positive integers. In other words, if elements constituting a matrix are 3, it represents a permutation matrix in which the identity matrix is shifted to the right three times.
FIG. 9 illustrates a method of expressing a matrix according to the aforementioned positive integers, i.e., shift numbers. It is assumed that a specific matrix H is expressed by a structured matrix of 4×4 (i.e., sub-block). In this case, if the specific sub block is expressed by 3, the sub-block becomes a matrix of FIG. 9.
Hereinafter, LDPC encoding method will be described.
According to a general LDPC encoding method, information bits are encoded by using a generation matrix G derived from an LDPC parity check matrix H. For generating the generation matrix Q the parity check matrix H is configured in the form of [PT:I] by using a Gaussian reduction method. Assuming the number of the information bits is ‘k’ and a size of an encoded codeword is ‘n’, the ‘P’ is a matrix having ‘k’ number of rows and ‘(n−k)’ number of columns and the ‘I’ is an identity matrix having ‘k’ number of rows and columns.
When the parity check matrix H is represented in the form of [PT:I], the generation matrix G has the form of [I:P]. The information bits of k bits to be encoded can be represented as a matrix ‘x’ having one row and ‘k’ number of columns. In this case, the codeword ‘c’ is represented in the form of the following equation.c=xG=[x:xP]
In the above equation, x represents a systematic part, and xP represents a parity part.
Meanwhile, if encoding is performed by the Gaussian Reduction method as above, since a calculation amount is increased, the form of the matrix H is designed in a specific structure so that a method of directly encoding data in the matrix H without deriving the matrix G is used. In other words, if the equation 1 is multiplied by HT by using a feature (i.e., GHT=0) that a product between the matrix G and a transpose HT for the matrix H, the following equation 2 can be obtained. The codeword ‘c’ can be obtained by adding a parity bit suitable for the equation 2 next to the information bit ‘x.’cHT=xGHT=[x:xP][PT:I]T=0  [Equation 2]
Hereinafter, LDPC decoding method will be described.
Data encoded in a communication system includes noise when passing through a radio channel of FIG. 1. A receiver represents a decoding procedure of data through a procedure as shown in FIG. 10. A decoding block of the receiver obtains an information bit ‘x’ from a receiving signal c′having the encoded codeword ‘c’ added with noise by using the feature of cHT=0. In other words, assuming that the received codeword is c′, a value of c′HT is calculated. As a result, if the value of c′HT is 0, first k number of bits from c′ are determined as the information bit x. If the value of c′HT is not 0, c′ which satisfies c′HT of 0 is searched by using a decoding method of a sum-product algorithm through a graph, thereby restoring the information bit x.
Hereinafter, a coding rate of LDPC coding will be described.
Generally, when the size of the information bit is k and the size of the codeword which is actually transmitted is n, a coding rate (R) is as follows.R=k/n  [Equation 3]
When the matrix H necessary for LDPC encoding and decoding has a row size of m and a column size of n, a coding rate is as follows.R=1−m/n  [Equation 4]
As described above, since the related art LDPC code is encoded and decoded by the matrix H, the structure of the matrix H is very important. In other words, since encoding and decoding performance is greatly affected by the structure of the matrix H, design of the matrix H is more important than anything else.
Hereinafter, the related art problems will be described.
The related art, for example, the LDPC encoding method of IEEE 802.16e, supports various coding rates. To this end, a parity check matrix or a model matrix corresponding to each coding rate is stored in an encoder. For example, since IEEE 802.16e supports a coding rate of 1/2, 2/3A, 2/3B, 3/4A, and 5/6, a model matrix according to each coding rate is stored in the memory.
TABLE 1CodingTotal nonzero weightrateat model matrix1/2762/3A802/3B813/4A853/4B885/680
In the LDPC encoding or decoding method according to the related art, since a plurality of model matrixes are used, many memories are required in the transmitter and the receiver, and it is difficult to apply the LDPC encoding or decoding method to various kinds of data retransmission methods such as ARQ or HARQ. For example, if data retransmission is performed in accordance with the IR method, a coding rate during initial transmission should be different from that during retransmission. To use different coding rates, encoding should be performed through different model matrixes. In other words, since a first model matrix used during initial transmission is different from a second model matrix used after reception of a NACK, a parity bit generated by the first model matrix becomes different from that generated by the second model matrix, thereby making combining reception in the receiver impossible.